{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reference: http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.12.html\n",
    "\n",
    "Clark-Wright Savings Algorithm (Algorithm 6.7)\n",
    "- STEP \t1: \tCalculate the savings s(i, j) = d(D, i) + d(D, j) - d(i, j) for every pair (i, j) of demand nodes.\n",
    "- STEP \t2: \tRank the savings s(i, j) and list them in descending order of magnitude. This creates the \"savings list.\" Process the savings list beginning with the topmost entry in the list (the largest s(i, j)).\n",
    "- STEP \t3: \tFor the savings s(i, j) under consideration, include link (i, j) in a route if no route constraints will be violated through the inclusion of (i, j) in a route, and if:\n",
    "\n",
    "     a. Either, neither i nor j have already been assigned to a route, in which case a new route is initiated including both i and j.\n",
    "\n",
    "     b. Or, exactly one of the two nodes (i or j) has already been included in an existing route and that point is not interior to that route (a point is interior to a route if it is not adjacent to the depot D in the order of traversal of nodes), in which case the link (i, j) is added to that same route.\n",
    "\n",
    "     c. Or, both i and j have already been included in two different existing routes and neither point is interior to its route, in which case the two routes are merged.\n",
    "     \n",
    "\n",
    "- STEP \t4: \tIf the savings list s(i, j) has not been exhausted, return to Step 3, processing the next entry in the list; otherwise, stop: the solution to the VRP consists of the routes created during Step 3. (Any nodes that have not been assigned to a route during Step 3 must each be served by a vehicle route that begins at the depot D visits the unassigned point and returns to D.) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>d0</th>\n",
       "      <th>demand</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>node</th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>1</td>\n",
       "      <td>25</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>2</td>\n",
       "      <td>43</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>3</td>\n",
       "      <td>57</td>\n",
       "      <td>5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>4</td>\n",
       "      <td>43</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      d0  demand\n",
       "node            \n",
       "0      0       0\n",
       "1     25       4\n",
       "2     43       6\n",
       "3     57       5\n",
       "4     43       4"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# read node data in coordinate (x,y) format\n",
    "nodes = pd.read_csv('input/demand.csv', index_col = 'node')\n",
    "nodes.rename(columns={\"distance to depot\":'d0'}, inplace = True)\n",
    "node_number = len(nodes.index) - 1\n",
    "nodes.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "      <th>5</th>\n",
       "      <th>6</th>\n",
       "      <th>7</th>\n",
       "      <th>8</th>\n",
       "      <th>9</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>29</td>\n",
       "      <td>34</td>\n",
       "      <td>43</td>\n",
       "      <td>68</td>\n",
       "      <td>49</td>\n",
       "      <td>66</td>\n",
       "      <td>72</td>\n",
       "      <td>91</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>2</td>\n",
       "      <td>29</td>\n",
       "      <td>0</td>\n",
       "      <td>52</td>\n",
       "      <td>72</td>\n",
       "      <td>96</td>\n",
       "      <td>72</td>\n",
       "      <td>81</td>\n",
       "      <td>89</td>\n",
       "      <td>114</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>3</td>\n",
       "      <td>34</td>\n",
       "      <td>52</td>\n",
       "      <td>0</td>\n",
       "      <td>45</td>\n",
       "      <td>71</td>\n",
       "      <td>71</td>\n",
       "      <td>95</td>\n",
       "      <td>99</td>\n",
       "      <td>108</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>4</td>\n",
       "      <td>43</td>\n",
       "      <td>72</td>\n",
       "      <td>45</td>\n",
       "      <td>0</td>\n",
       "      <td>27</td>\n",
       "      <td>36</td>\n",
       "      <td>65</td>\n",
       "      <td>65</td>\n",
       "      <td>65</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>5</td>\n",
       "      <td>68</td>\n",
       "      <td>96</td>\n",
       "      <td>71</td>\n",
       "      <td>27</td>\n",
       "      <td>0</td>\n",
       "      <td>40</td>\n",
       "      <td>66</td>\n",
       "      <td>62</td>\n",
       "      <td>46</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>6</td>\n",
       "      <td>49</td>\n",
       "      <td>72</td>\n",
       "      <td>71</td>\n",
       "      <td>36</td>\n",
       "      <td>40</td>\n",
       "      <td>0</td>\n",
       "      <td>31</td>\n",
       "      <td>31</td>\n",
       "      <td>43</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>7</td>\n",
       "      <td>66</td>\n",
       "      <td>81</td>\n",
       "      <td>95</td>\n",
       "      <td>65</td>\n",
       "      <td>66</td>\n",
       "      <td>31</td>\n",
       "      <td>0</td>\n",
       "      <td>11</td>\n",
       "      <td>46</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>8</td>\n",
       "      <td>72</td>\n",
       "      <td>89</td>\n",
       "      <td>99</td>\n",
       "      <td>65</td>\n",
       "      <td>62</td>\n",
       "      <td>31</td>\n",
       "      <td>11</td>\n",
       "      <td>0</td>\n",
       "      <td>36</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>9</td>\n",
       "      <td>91</td>\n",
       "      <td>114</td>\n",
       "      <td>108</td>\n",
       "      <td>65</td>\n",
       "      <td>46</td>\n",
       "      <td>43</td>\n",
       "      <td>46</td>\n",
       "      <td>36</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    1    2    3   4   5   6   7   8    9\n",
       "                                        \n",
       "1   0   29   34  43  68  49  66  72   91\n",
       "2  29    0   52  72  96  72  81  89  114\n",
       "3  34   52    0  45  71  71  95  99  108\n",
       "4  43   72   45   0  27  36  65  65   65\n",
       "5  68   96   71  27   0  40  66  62   46\n",
       "6  49   72   71  36  40   0  31  31   43\n",
       "7  66   81   95  65  66  31   0  11   46\n",
       "8  72   89   99  65  62  31  11   0   36\n",
       "9  91  114  108  65  46  43  46  36    0"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# read pairwise distance\n",
    "pw = pd.read_csv('input/pairwise.csv', index_col = 'Unnamed: 0')\n",
    "pw.index.rename('',inplace = True)\n",
    "pw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>saving</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <td>(9,5)</td>\n",
       "      <td>86</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>(9,8)</td>\n",
       "      <td>83</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>(8,7)</td>\n",
       "      <td>78</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>(5,4)</td>\n",
       "      <td>77</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <td>(9,7)</td>\n",
       "      <td>66</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       saving\n",
       "(9,5)      86\n",
       "(9,8)      83\n",
       "(8,7)      78\n",
       "(5,4)      77\n",
       "(9,7)      66"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# calculate savings for each link\n",
    "savings = dict()\n",
    "for r in pw.index:\n",
    "    for c in pw.columns:\n",
    "        if int(c) != int(r):            \n",
    "            a = max(int(r), int(c))\n",
    "            b = min(int(r), int(c))\n",
    "            key = '(' + str(a) + ',' + str(b) + ')'\n",
    "            savings[key] = nodes['d0'][int(r)] + nodes['d0'][int(c)] - pw[c][r]\n",
    "\n",
    "# put savings in a pandas dataframe, and sort by descending\n",
    "sv = pd.DataFrame.from_dict(savings, orient = 'index')\n",
    "sv.rename(columns = {0:'saving'}, inplace = True)\n",
    "sv.sort_values(by = ['saving'], ascending = False, inplace = True)\n",
    "sv.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# convert link string to link list to handle saving's key, i.e. str(10, 6) to (10, 6)\n",
    "def get_node(link):\n",
    "    link = link[1:]\n",
    "    link = link[:-1]\n",
    "    nodes = link.split(',')\n",
    "    return [int(nodes[0]), int(nodes[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# determine if a node is interior to a route\n",
    "def interior(node, route):\n",
    "    try:\n",
    "        i = route.index(node)\n",
    "        # adjacent to depot, not interior\n",
    "        if i == 0 or i == (len(route) - 1):\n",
    "            label = False\n",
    "        else:\n",
    "            label = True\n",
    "    except:\n",
    "        label = False\n",
    "    \n",
    "    return label"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# merge two routes with a connection link\n",
    "def merge(route0, route1, link):\n",
    "    if route0.index(link[0]) != (len(route0) - 1):\n",
    "        route0.reverse()\n",
    "    \n",
    "    if route1.index(link[1]) != 0:\n",
    "        route1.reverse()\n",
    "        \n",
    "    return route0 + route1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# sum up to obtain the total passengers belonging to a route\n",
    "def sum_cap(route):\n",
    "    sum_cap = 0\n",
    "    for node in route:\n",
    "        sum_cap += nodes.demand[node]\n",
    "    return sum_cap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# determine 4 things:\n",
    "# 1. if the link in any route in routes -> determined by if count_in > 0\n",
    "# 2. if yes, which node is in the route -> returned to node_sel\n",
    "# 3. if yes, which route is the node belongs to -> returned to route id: i_route\n",
    "# 4. are both of the nodes in the same route? -> overlap = 1, yes; otherwise, no\n",
    "def which_route(link, routes):\n",
    "    # assume nodes are not in any route\n",
    "    node_sel = list()\n",
    "    i_route = [-1, -1]\n",
    "    count_in = 0\n",
    "    \n",
    "    for route in routes:\n",
    "        for node in link:\n",
    "            try:\n",
    "                route.index(node)\n",
    "                i_route[count_in] = routes.index(route)\n",
    "                node_sel.append(node)\n",
    "                count_in += 1\n",
    "            except:\n",
    "                a = 1\n",
    "                \n",
    "    if i_route[0] == i_route[1]:\n",
    "        overlap = 1\n",
    "    else:\n",
    "        overlap = 0\n",
    "        \n",
    "    return node_sel, count_in, i_route, overlap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "step  1 :\n",
      "\t Link  [9, 5]  fulfills criteria a), so it is created as a new route\n",
      "\t route:  [9, 5]  with load  11\n",
      "step  2 :\n",
      "\t Link  [9, 8]  fulfills criteria b), so a new node is added to route  [9, 5] .\n",
      "\t route:  [8, 9, 5]  with load  15\n",
      "step  3 :\n",
      "\t Link  [8, 7]  fulfills criteria b), so a new node is added to route  [8, 9, 5] .\n",
      "\t route:  [7, 8, 9, 5]  with load  20\n",
      "step  4 :\n",
      "\t Though Link  [5, 4]  fulfills criteria b), it exceeds maximum load, so skip this link.\n",
      "step  5 :\n",
      "\t Link  [9, 7]  is already included in the routes\n",
      "step  6 :\n",
      "\t For Link  [9, 6] , node  9  is interior to route  [7, 8, 9, 5] , so skip this link\n",
      "step  7 :\n",
      "\t Link  [4, 3]  fulfills criteria a), so it is created as a new route\n",
      "\t route:  [7, 8, 9, 5]  with load  20\n",
      "\t route:  [4, 3]  with load  9\n",
      "step  8 :\n",
      "\t Link  [6, 5]  fulfills criteria b), so a new node is added to route  [7, 8, 9, 5] .\n",
      "\t route:  [7, 8, 9, 5, 6]  with load  23\n",
      "\t route:  [4, 3]  with load  9\n",
      "step  9 :\n",
      "\t For link  [9, 4] , Two nodes are found in two different routes, but not all the nodes fulfill interior requirement, so skip this link\n",
      "step  10 :\n",
      "\t Link  [3, 2]  fulfills criteria b), so a new node is added to route  [4, 3] .\n",
      "\t route:  [7, 8, 9, 5, 6]  with load  23\n",
      "\t route:  [4, 3, 2]  with load  15\n",
      "step  11 :\n",
      "\t For Link  [3, 1] , node  3  is interior to route  [4, 3, 2] , so skip this link\n",
      "step  12 :\n",
      "\t Link  [8, 5]  is already included in the routes\n",
      "step  13 :\n",
      "\t For link  [5, 3] , Two nodes are found in two different routes, but not all the nodes fulfill interior requirement, so skip this link\n",
      "step  14 :\n",
      "\t Link  [8, 6]  is already included in the routes\n",
      "step  15 :\n",
      "\t Link  [7, 6]  is already included in the routes\n",
      "step  16 :\n",
      "\t Link  [2, 1]  fulfills criteria b), so a new node is added to route  [4, 3, 2] .\n",
      "\t route:  [7, 8, 9, 5, 6]  with load  23\n",
      "\t route:  [4, 3, 2, 1]  with load  19\n",
      "-------\n",
      "All nodes are included in the routes, algorithm closed\n",
      "------\n",
      "Routes found are: \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[0, 7, 8, 9, 5, 6, 0], [0, 4, 3, 2, 1, 0]]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "    # create empty routes\n",
    "    routes = list()\n",
    "    \n",
    "    # if there is any remaining customer to be served\n",
    "    remaining = True\n",
    "    \n",
    "    # determine capacity of the vehicle\n",
    "    cap = 23\n",
    "    \n",
    "    # record steps\n",
    "    step = 0\n",
    "    \n",
    "    # get a list of nodes, excluding the depot\n",
    "    node_list = list(nodes.index)\n",
    "    node_list.remove(0)\n",
    "    \n",
    "    # run through each link in the saving list\n",
    "    for link in sv.index:\n",
    "        step += 1\n",
    "        if remaining:\n",
    "\n",
    "            print('step ', step, ':')\n",
    "\n",
    "            link = get_node(link)\n",
    "            node_sel, num_in, i_route, overlap = which_route(link, routes)\n",
    "\n",
    "            # condition a. Either, neither i nor j have already been assigned to a route, \n",
    "            # ...in which case a new route is initiated including both i and j.\n",
    "            if num_in == 0:\n",
    "                if sum_cap(link) <= cap:\n",
    "                    routes.append(link)\n",
    "                    node_list.remove(link[0])\n",
    "                    node_list.remove(link[1])\n",
    "                    print('\\t','Link ', link, ' fulfills criteria a), so it is created as a new route')\n",
    "                else:\n",
    "                    print('\\t','Though Link ', link, ' fulfills criteria a), it exceeds maximum load, so skip this link.')\n",
    "\n",
    "            # condition b. Or, exactly one of the two nodes (i or j) has already been included \n",
    "            # ...in an existing route and that point is not interior to that route \n",
    "            # ...(a point is interior to a route if it is not adjacent to the depot D in the order of traversal of nodes), \n",
    "            # ...in which case the link (i, j) is added to that same route.    \n",
    "            elif num_in == 1:\n",
    "                n_sel = node_sel[0]\n",
    "                i_rt = i_route[0]\n",
    "                position = routes[i_rt].index(n_sel)\n",
    "                link_temp = link.copy()\n",
    "                link_temp.remove(n_sel)\n",
    "                node = link_temp[0]\n",
    "\n",
    "                cond1 = (not interior(n_sel, routes[i_rt]))\n",
    "                cond2 = (sum_cap(routes[i_rt] + [node]) <= cap)\n",
    "\n",
    "                if cond1:\n",
    "                    if cond2:\n",
    "                        print('\\t','Link ', link, ' fulfills criteria b), so a new node is added to route ', routes[i_rt], '.')\n",
    "                        if position == 0:\n",
    "                            routes[i_rt].insert(0, node)\n",
    "                        else:\n",
    "                            routes[i_rt].append(node)\n",
    "                        node_list.remove(node)\n",
    "                    else:\n",
    "                        print('\\t','Though Link ', link, ' fulfills criteria b), it exceeds maximum load, so skip this link.')\n",
    "                        continue\n",
    "                else:\n",
    "                    print('\\t','For Link ', link, ', node ', n_sel, ' is interior to route ', routes[i_rt], ', so skip this link')\n",
    "                    continue\n",
    "\n",
    "            # condition c. Or, both i and j have already been included in two different existing routes \n",
    "            # ...and neither point is interior to its route, in which case the two routes are merged.        \n",
    "            else:\n",
    "                if overlap == 0:\n",
    "                    cond1 = (not interior(node_sel[0], routes[i_route[0]]))\n",
    "                    cond2 = (not interior(node_sel[1], routes[i_route[1]]))\n",
    "                    cond3 = (sum_cap(routes[i_route[0]] + routes[i_route[1]]) <= cap)\n",
    "\n",
    "                    if cond1 and cond2:\n",
    "                        if cond3:\n",
    "                            route_temp = merge(routes[i_route[0]], routes[i_route[1]], node_sel)\n",
    "                            temp1 = routes[i_route[0]]\n",
    "                            temp2 = routes[i_route[1]]\n",
    "                            routes.remove(temp1)\n",
    "                            routes.remove(temp2)\n",
    "                            routes.append(route_temp)\n",
    "                            node_list.remove(link[0])\n",
    "                            node_list.remove(link[1])\n",
    "                            print('\\t','Link ', link, ' fulfills criteria c), so route ', temp1, ' and route ', temp2, ' are merged')\n",
    "                        else:\n",
    "                            print('\\t','Though Link ', link, ' fulfills criteria c), it exceeds maximum load, so skip this link.')\n",
    "                            continue\n",
    "                    else:\n",
    "                        print('\\t','For link ', link, ', Two nodes are found in two different routes, but not all the nodes fulfill interior requirement, so skip this link')\n",
    "                        continue\n",
    "                else:\n",
    "                    print('\\t','Link ', link, ' is already included in the routes')\n",
    "                    continue\n",
    "\n",
    "            for route in routes: \n",
    "                print('\\t','route: ', route, ' with load ', sum_cap(route))\n",
    "        else:\n",
    "            print('-------')\n",
    "            print('All nodes are included in the routes, algorithm closed')\n",
    "            break\n",
    "\n",
    "        remaining = bool(len(node_list) > 0)\n",
    "\n",
    "    # check if any node is left, assign to a unique route\n",
    "    for node_o in node_list:\n",
    "        routes.append([node_o])\n",
    "\n",
    "    # add depot to the routes\n",
    "    for route in routes:\n",
    "        route.insert(0,0)\n",
    "        route.append(0)\n",
    "\n",
    "    print('------')\n",
    "    print('Routes found are: ')\n",
    "    routes\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check this result with the textbook link above. Remember to offset by 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
